package com.qf.pojo.day03;

/**
 *
 * 一棵二叉  搜索树，
 *      先序遍历结果为：5  2  1  3  4  6  8  7  9
 *      求后序遍历结果。
 *  1、画树
 *  2、代码
 * @author lixu
 */
public class TreeSortDemo {

    /**
     *  树的数据结构
     * @param <T>
     */
    private static class Node<T>{
       // T index;//索引= 正文的页号
        T value;//值   1-9    a-y  chan
        Node<T> left;
        Node<T> right;

        public Node(T value) {
            this.value = value;
        }
    }


    public static void main(String[] args) {
        //准备了一个原始数据
        int[] arr = new int[]{5,2,1,3,4,6,8,7,9};

        //0:准备一颗树
        Node tree = new Node(arr[0]);
        //1:代码先生成一颗树
        for (int i = 1; i <arr.length ; i++) {
            //有树的情况下 插入其它的子节点
            insertTree(tree,arr[i]);
        }

        //2:验证此树是正确的？
/*        System.out.println(tree.right.right.right.value);
        System.out.println(tree.left.right.right.value);
        System.out.println(tree.left.left.value);*/
        //3:求后序遍历结果。
        //printTree(tree);
        //4:从当前这颗树中 查询是否存在9
        System.out.println("是否存在:" + searchTree(tree,23));

    }

    /**
     * 搜索这颗树
     * @param tree
     * @param value
     * @return
     */
    private static boolean searchTree(Node<Integer> tree, int value) {
        //1:判断根节点
        if(tree.value == value){
            return true;//存在的
        }
        //2:判断大小
        if(tree.value > value){
            //3:左子树
            if(tree.left!=null) return searchTree(tree.left,value);

        }else{
            //4:右子树
            if(tree.right!=null) return searchTree(tree.right,value);
        }
        //    不存在
        return false;

    }

    /**
     * 求后序遍历结果。 ==  左子树 、右子树、 根
     *
     *
     *
     *
     * 求先序遍历结果  根、左子树、右子树
     * 先序遍历结果为：5  2  1  3  4  6  8  7  9
     * --------------------------------------
     * 求后序遍历结果。 ==  左子树 、右子树、 根
     *         1 4 3 2 7 9 8 6 5
     * @param tree
     */
    private static void printTree(Node tree) {
        //1:左子树
        if(tree.left!=null){
            printTree(tree.left);
        }
        //2：右子树
        if(tree.right!=null){
            printTree(tree.right);
        }
        //3:根
        System.out.print(tree.value + " ");
    }

    /**
     * 算法： 将value元素插入到树中节点上    树 O(logn)  < O(n)链表
     * @param tree
     * @param value
     */
    private static void insertTree(Node<Integer> tree, int value) {
         if(tree.value > value){
            //将value元素插入到左子树中
             //判断是否有左子树、
             if(tree.left==null){
                 //--没有
                 tree.left = new Node(value);
             }else{
                 //--有
                 insertTree(tree.left,value);//递归
             }
         }else{
             //将value元素插入到右子树中
             //判断是否有右子树、
             if(tree.right==null){
                 //--没有
                 tree.right = new Node(value);
             }else{
                 //--有
                 insertTree(tree.right,value);
             }
         }
    }
}
